import random
import heapq
import time

# EXERCICE 1

# Fonction CreationListe(n,min,max)

def CreationListe(n,min,max):
    return [random.randint(min, max+1) for i in range(n)]

# Création du tas heap
data = CreationListe(10,1,101)
print(data)                 # [10, 42, 14, 23, 6, 55, 13, 62, 64, 85]

heapq.heapify(data)
print(data)                 # [6, 10, 13, 23, 42, 55, 14, 62, 64, 85]

# La structure du tas est respectée :
#                 6
#              /     \
#           10         13
#         /    \      /   \
#       23     42   55    14
#      /  \
#    62   64
#   /
# 85

# EXERCICE 2
heapq.heappush(data,0)      # O(log n) ; avec une liste triée classique : O(n)
print(data)                 # [0, 6, 13, 23, 10, 55, 14, 62, 64, 85, 42]
                            # Le 0 est bien inséré en t^te et la strcture du tas a été réoganisée
#                     0
#                  /     \
#               6          13
#             /   \       /   \
#           23     10   55     14
#          /  \    /
#        62   64 85  42


min_val = heapq.heappop(data)   # O(log n) ; avec une liste triée classique : O(n) car il faut décaler tous les éléments après
print(min_val)
print(data)

print(data[0])                  # Complexité en O(1), comme pour une liste triée standard

# EXERCICE 3

def test_insertion_liste(n):
    L = []
    start = time.time()
    for i in range(n):
        L.append(random.randint(0, n))
    end = time.time()
    print(f"Insertion dans une liste ({n} éléments) : {end - start:.6f} s")

test_insertion_liste(1000000)              # 0.212325 s

def test_insertion_tas(n):
    H = []
    heapq.heapify(H)
    start = time.time()
    for i in range(n):
        heapq.heappush(H, random.randint(0, n))
    end = time.time()
    print(f"Insertion dans un tas ({n} éléments) : {end - start:.6f} s")

test_insertion_tas(1000000)              # 0.24 s

# La durée d'execution est plus lente avec le tas O(logn) qu'avec la liste O(1) car le tas doit réorganiser les données
# alors que la liste insère la donnée à la fin.

# EXERCICE 4

def test_insertion_liste_avec_tri(n):
    L = []
    start = time.time()
    for i in range(n):
        x = random.randint(0, n)
        L.append(x)
        L.sort()
    end = time.time()
    print(f"Insertion dans une liste triée ({n} éléments) : {end - start:.6f} s")

test_insertion_liste_avec_tri(10000)    # 0.087482 s
test_insertion_tas(10000)               # 0.002594 s

# La durée d'execution est cette fois-ci beaucoup plus longue dans le cas de la liste triée.
# Cas d'une liste triée : L.append(x) + L.sort() : O(1) + O(n log n) = O(nlogn) à chaque insertion donc au total O(n²log n)
# Cas du tas : O(logn) à chaque insertion donc O(nlogn) au total

# EXERCICE 5
liste = CreationListe(1000000,0,1000000)

# min() sur une liste non triée
start = time.time()
val_min = min(liste)
end = time.time()
print(f"Recherche min dans liste : {end - start:.6f}s")     # 0.005389s - O(n) : O(n) pour trouver la plus petite valeur en parcourant les éléments
                                                            # + O(n) pour la supprimer car il faut réaranger la liste ensuite => O(n) au total

# heappop sur un tas
start = time.time()
tas = heapq.heappop(liste)
end = time.time()
print(f"Extraction min dans tas : {end - start:.6f}s")      # 0.000003s - O(logn) : extraction de la racine qui est le minimum O(1)
                                                            # + remplacer la racine par le dernier élément du tas O(1)
                                                            # faire descendre cet élément (“heapify down”) jusqu’à retrouver la bonne position pour que la propriété du tas soit respectée = O(log2(n))



# EXERCICE 6
tas = []

heapq.heappush(tas, (5, 'A'))
heapq.heappush(tas, (3, 'B'))
heapq.heappush(tas, (8, 'C'))
heapq.heappush(tas, (1, 'D'))

print(tas)                          # [(1, 'D'), (3, 'B'), (8, 'C'), (5, 'A')]

#                  (1, 'D')
#                 /         \
#           (3, 'B')       (8, 'C')
#             /
#         (5, 'A')

print(heapq.heappop(tas))           # (1,'D') : C'est l'élément avec la clé minimale
                                    # Utlile dans l'algorithme de Dijkstra pour calculer les distances minimale qui seront les clés des tas